#include<bits/stdc++.h>

using namespace std;
using ll = long long;
#define endl '\n'

bool prime(int n) {//定义O(n)
    //如果在[2,n-1]之间找不到因子 就是素数，否则就不是
    for (int i = 2; i <= n - 1; i++) {
        if (n % i == 0)
            return false;
    }
    return true;
}

bool prime1(int n) {//定义O(n/2)
    //如果在[2,n/2]之间找不到因子 就是素数，否则就不是
    for (int i = 2; i <= n / 2; i++) {
        if (n % i == 0)
            return false;
    }
    return true;
}

bool prime2(int n) {//O(sqrt(n))
    //如果在[2,sqrt(n)]之间找不到因子 就是素数，否则就不是
    for (int i = 2, m = sqrt(n); i <= m; i++) {
        if (n % i == 0)
            return false;
    }
    return true;
}
bool prime3(int n) {
    //如果在[3,sqrt(n)]之间找不到因子 就是素数，否则就不是
    if(n==2)return true;
    if(n<2||n%2==0)return false;
    for (int i = 3, m = sqrt(n); i <= m; i+=2) {
        if (n % i == 0)
            return false;
    }
    return true;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    ll start = clock();
    for (int i = 0; i < 1e6; i++) {
        if (prime3(i)) {
            // cout << i << " ";
        }
    }

    ll end = clock();

    cerr << "It elapsed " << 1.0 * (end - start) / CLOCKS_PER_SEC << " second(s)." << endl;


    return 0;
}
